class Solution:
    """
    从前往后dp做不了，因为从前走得到的最优路径，后面可能走不通，比如
    [[0, 0],
     [-2, 0],
     [10, 0]]
    前面有两条比较好的路，一条是[0，0，0，0]，初始生命值是1就行，另一条是[0，-2，10，0]，初始生命值要为3，如果只考虑当前走到[2][1]的话，肯定选[0，0，0，0]这条路，
    初始生命值是1就可以，但是如果继续往下考虑，补全矩阵为
    [[0, 0, 0],
     [-2, 0, 0],
     [10, 0, -5]]
     前面的路就应该选择[0, -2, 10, 0, -5]了，因为再往下走遇到了-5，[0, -2, 10, 0, -5]路上有个10，-5之前这段的累加值比[0, 0, 0, 0, -5]高，也就是说正向dp，不只要考虑需要的初始生命值最小，还要同时考虑到一路上的累加值够大，这就没法dp了。
     这主要是因为后面的路会影响我们对前面的路的选择，所以dp不好使了，大问题拆解不成小问题。

     那么换个思路，既然后面的路会影响前面的路，那前面的路会影响后面的路吗？也就是说如果已经想好了后面该怎么走，前面的路发生变化了会影响后面的走法吗？这么一看就发现并不会。
     比如后面的路是[0，0，0，0]和[0，-2，10，0]，我们选了第一条路，那么我们在前面不管加一个什么数，也就是[x, 0, 0, 0, 0]和[x，0，-2，10，0]，我们一定还是选之前选的第一条路。（可以用数学证明）
    """

    def calculateMinimumHP(self, dungeon):
        m, n = len(dungeon), len(dungeon[0])
        # 初始化
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[-1][-1] = max(-dungeon[-1][-1], 0) + 1  # 至少得活着，故最少得是1血
        for i in range(len(dp)-2, -1, -1):
            dp[i][-1] = max(dp[i+1][-1] - dungeon[i][-1], 1)
        for i in range(len(dp[0])-2, -1, -1):
            dp[-1][i] = max(dp[-1][i+1] - dungeon[-1][i], 1)

        
        for row in range(len(dp)-2, -1, -1):
            for col in range(len(dp[0])-2, -1, -1):
                dp[row][col] = max(min(dp[row+1][col], dp[row][col+1]) - dungeon[row][col], 1)

        return dp[0][0]
